#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>

//void printyhsj(int* arr, int n) {
//	arr[0] = 1;
//	printf("1\n");
//	for (int i = 1; i < n; ++i) {
//		for (int j = i; j > 0; --j) {
//			arr[j] += arr[j - 1];
//		}
//
//		for (int j = 0; j <= i; j++) {
//			printf("%d ", arr[j]);
//		}
//		printf("\n");
//	}
//}

//void printyhsj(int** arr, int n) {
//	for (int i = 0; i < n; ++i) {
//		for (int j = 0; j <= i; ++j) {
//			if (j == 0 || i == j) {
//				arr[i][j] = 1;
//			}
//			else {
//				arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
//			}
//		}
//	}
//
//
//	for (int i = 0; i < n; ++i) {
//		for (int j = 0; j <= i; ++j) {
//			printf("%d ", arr[i][j]);
//		}
//		printf("\n");
//	}
//}

void printyhsj(int* arr, int n) {
	arr[0] = 1;
	printf("1\n");
	for (int i = 1; i < n; ++i) {
		for (int j = i; j > 0; j--) {
			arr[j] += arr[j - 1];
		}

		for (int j = 0; j <= i; ++j) {
			printf("%d ", arr[j]);
		}
		printf("\n");
	}
}

//日本某地发生了一件谋杀案，警察通过排查确定杀人凶手必为4个嫌疑犯的一个。
//以下为4个嫌疑犯的供词 :
//A说：不是我。
//B说：是C。
//C说：是D。
//D说：C在胡说
//已知3个人说了真话，1个人说的是假话。
//现在请根据这些信息，写一个程序来确定到底谁是凶手。

void GuessK() {
	char ker = 0;
	for (char ker = 'a'; ker <= 'd'; ++ker) {
		if (((ker != 'a') + (ker == 'c') + (ker == 'd') + (ker != 'd')) == 3) {
			printf("%c \n", ker);
		}
	}
}

//5位运动员参加了10米台跳水比赛，有人让他们预测比赛结果：
//A选手说：B第二，我第三；
//B选手说：我第二，E第四；
//C选手说：我第一，D第二；
//D选手说：C最后，我第三；
//E选手说：我第四，A第一；
//比赛结束后，每位选手都说对了一半，请编程确定比赛的名次。

void GuessN() {
	for (int A = 0; A <= 5; ++A) {
		for (int B = 0; B <= 5; ++B) {
			for (int C = 0; C <= 5; ++C) {
				for (int D = 0; D <= 5; ++D) {
					for (int E = 0; E <= 5; ++E) {
						if ((((B == 2) + (A == 3)) == 1) &&
							(((B == 2) + (E == 4)) == 1) &&
							(((C == 1) + (D == 2)) == 1) &&
							(((C == 5) + (D == 3)) == 1) &&
							(((E == 4) + (A == 1)) == 1) &&
							(A * B * C * D * E == 120)) {
							printf("a = %d , b = %d , c = %d, d = %d, e = %d \n", A, B, C, D, E);
						}
					}
				}
			}
		}
	}
}

//杨氏矩阵
// 1 2 3
// 4 5 6
// 7 8 9

void yangshijz(int arr[][3], int* px, int* py, int key) {
	int x = 0;
	int y = *px - 1;

	while (x < *px && y >= 0) {
		if (arr[x][y] < key) {
			x++;
		}
		else if (arr[x][y] > key) {
			y--;
		}
		else {
			*px = x;
			*py = y;
			return;
		}
	}

	*px = -1;
	*py = -1;
}


//实现一个函数，可以左旋字符串中的k个字符。
//ABCD左旋一个字符得到BCDA
//ABCD左旋两个字符得到CDAB


//void leftRound(char* str, int k) {
//	int len = strlen(str);
//	k %= len;
//	
//	while (k--) {
//		char tmp = *str;
//		for (int i = 0; i < len - 1; ++i) {
//			*(str + i) = *(str + i + 1);
//		}
//		*(str + len - 1) = tmp;
//	}
//}

void reverse(char* left, char* right) {
	while (left < right) {
		char tmp = *left;
		*left = *right;
		*right = tmp;

		left++;
		right--;
	}
}

void leftRound(char* str, int k) {
	int len = strlen(str);
	k %= len;

	reverse(str, str + k - 1);
	reverse(str + k, str + len - 1);
	reverse(str, str + len - 1);
}

//写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。
//例如：给定s1 = AABCD和s2 = BCDAA，返回1
//给定s1 = abcd和s2 = ACBD，返回0
//AABCD左旋一个字符得到ABCDA
//AABCD左旋两个字符得到BCDAA
//AABCD右旋一个字符得到DAABC

//int findRound(const char* str1, char* str2) {
//	int len = strlen(str2);
//	int j = len;
//	while (j--) {
//		char tmp = *str2;
//		for (int i = 0; i < len - 1; ++i) {
//			*(str2 + i) = *(str2 + i + 1);
//		}
//		*(str2 + len - 1) = tmp;
//
//		if (strcmp(str1, str2) == 0) {
//			return 1;
//		}
//	}
//	return 0;
//}

int findRound(const char* str1, char* str2) {
	int len1 = strlen(str1);
	int len2 = strlen(str2);

	if (len1 != len2) {
		return 0;
	}

	char tmp[256] = "";
	strcpy(tmp, str1);
	strcat(tmp, str1);

	if (strstr(tmp,str2) == NULL) {
		return 0;
	}
	else {
		return 1;
	}
}

//一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
//编写一个函数找出这两个只出现一次的数字。
//例如：
//有数组的元素是：1，2，3，4，5，1，2，3，4，6
//只有5和6只出现1次，要找出5和6

void findTwoNum(int arr[], int n, int* pdog1, int* pdog2) {
	//先把全部数异或在一起
	int ret = 0;
	for (int i = 0; i < n; ++i) {
		ret ^= arr[i];
	}
	//找到两个狗异或在一起的二进制位的第一位的下标
	int pos = 0;
	for (int i = 0; i < 32; ++i) {
		if (((ret >> i) & 1) == 1) {
			pos = i;
			break;
		}
	}

	//根据pos位置的不同，把数分为两个组
	for (int i = 0; i < n; ++i) {
		if (((arr[i] >> pos) & 1 == 1)) {
			*(pdog1) ^= arr[i];
		}
		else {
			*(pdog2) ^= arr[i];
		}
	}
}


char* my_strstr(char* str1, char* str2) {
	char* c = str1;
	char* s1 = str1;
	char* s2 = str2;

	while (*c) {
		s1 = c;
		s2 = str2;
		while ((*s1 == *s2) && (*s1) && (*s2)) {
			s1++;
			s2++;
		}

		if (*s2 == "\0") {
			return c;
		}
		c++;
	}
	return NULL;
}


void* my_memmove(void* dst, const void* src, size_t num) {
	assert(dst && src);
	void* ret = dst;
	if (dst < src) {
		//从前往后
		while (num--) {
			*(char*)dst = *(char*)src;
			((char*)src)++;
			((char*)dst)++;
		}
	}
	else {
		//从后往前
		while (num--) {
			*((char*)dst + num) = *((char*)src + num);
		}
	}

	return ret;
}

#define OFFSETOF(type,member)   ((size_t)&(((type*)0)->member))

#define SWAP(n) ((n) = (((n&0xaaaaaaaa)>>1) + ((n&0x55555555)>>1)))

enum state {
	HF,
	FF
} state = FF;


int my_atoi(const char* str) {
	//传入空指针
	assert(str);
	int flag = 1;
	//传入空字符串
	if (*str == '\0') {
		return 0;
	}
	//传入空格
	while (isspace(*str)) {
		str++;
	}
	//传入+-
	if (*str == '+') {
		str++;
	}
	else if (*str == '-') {
		flag = -1;
		str++;
	}
	else {
		long long ret = 0;
		while (*str) {
			if (isdigit(*str)) {
				ret = ret * 10 + flag * (*str - '0');
				//计算结果非法
				if (ret < INT_MIN || ret > INT_MAX) {
					state = FF;
					return 0;
				}
			}
			else {
				//传入非数字字符
				state = FF;
				return ret;
			}
			str++;
		}
		//合法返回
		state = HF;
		return ret;
	}
}

void swap(char* s1, char* s2, int type_size) {
	while (type_size--) {
		char tmp = *s1;
		*s1 = *s2;
		*s2 = tmp;
		s1++;
		s2++;
	}
}

int cmp(void* c1, void* c2) {
	return *((int*)c1) - *((int*)c2);
}

void my_qsort(int arr[], int size, int type_size, int (*cmp)(void*, void*)) {
	for (int i = 0; i < size; ++i) {
		for (int j = 0; j < size - i - 1; ++j) {
			if (cmp(((char*)arr + (j * type_size)), ((char*)arr + ((j + 1) * type_size))) > 0) {
				swap(((char*)arr + (j * type_size)), ((char*)arr + ((j + 1) * type_size)), type_size);
			}
		}
	}
}

int main() {
	//int n;
	//scanf("%d", &n);
	////int** arr = (int**)malloc(sizeof(int*) * n);
	////for (int i = 0; i < n; ++i) {
	////	arr[i] = (int*)malloc(sizeof(int) * n);
	////}
	//int* arr = (int*)malloc(sizeof(int) * n);
	//memset(arr, 0, n * sizeof(int));
	//printyhsj(arr, n);
	//GuessN();

	//char str1[] = "abcdef";

	////leftRound(str1, 1);

	//printf("%s\n", str1);

	//char str2[] = "defabc";
	
	int arr[] = { 1,4,7,2,5,8,3,6,9,0 };
	
	my_qsort(arr, 10, 4, cmp);

	for (int i = 0; i < 10; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\n");



	return 0;
}